{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Derangement of An Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findDerangement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找数组的错位排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在组合数学中，如果一个排列中所有元素都不在原先的位置上，那么这个排列就被称为 <strong>错位排列</strong> 。</p>\n",
    "\n",
    "<p>给定一个从&nbsp;<code>1</code> 到 <code>n</code>&nbsp;升序排列的数组，返回&nbsp;<em><strong>不同的错位排列</strong> 的数量&nbsp;</em>。由于答案可能非常大，你只需要将答案对 <code>10<sup>9</sup>+7</code> <strong>取余</strong>&nbsp;输出即可。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 3\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 原始的数组为 [1,2,3]。两个错位排列的数组为 [2,3,1] 和 [3,1,2]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 2\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-derangement-of-an-array](https://leetcode.cn/problems/find-the-derangement-of-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-derangement-of-an-array](https://leetcode.cn/problems/find-the-derangement-of-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        # a(n+2) = (n+1)*a(n) + a(n+1)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        elif n==2:\n",
    "            return 1\n",
    "        a,b = 1,2 # n=2,n=3\n",
    "        for i in range(3,n):\n",
    "            a,b = b%mod,(i*(a+b))%mod\n",
    "        return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        \"\"\"\n",
    "            错排原理 \n",
    "            对于 1 - n 中的元素 k 而严 \n",
    "            将 k 放在pos = n  剩下n- 1 个元素有多少种错排的子问题\n",
    "                对于该子问题\n",
    "        \"\"\" \n",
    "        pre,last = 0,1\n",
    "        if n==1: return pre \n",
    "        for i in range(3,n+1):\n",
    "            tmp = (i-1)*(pre+last)%mod\n",
    "            pre =last\n",
    "\n",
    "            last =tmp\n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        # f(n) = (n - 1)*(f(n - 1) + f(n - 2))\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        MOD = 10**9 + 7\n",
    "        x,y = 0,1\n",
    "        for i in range(3,n + 1):\n",
    "            y,x = (i - 1)*(y + x)%MOD,y\n",
    "        \n",
    "        return y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        pre, cnt = 0, 1\n",
    "        if n == 1: return 0\n",
    "        if n == 2: return 1\n",
    "        for i in range(2, n):\n",
    "            pre, cnt = cnt, (pre + cnt) * (i) % int(1e9+7)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        answer = 0\n",
    "        for i in range(n+1):\n",
    "            answer = int((i*answer+(-1)**i)%(1e9+7))\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(n + 1):\n",
    "            res = (i * res + (-1) ** i) % (10 ** 9 + 7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        #动态规划f(n) = (n - 1) * (f(n - 1) + f(n - 2)),f(n-2)的情况代表两数对调,f(n-1)的情况代表非对调情况\n",
    "        #初始情况n=2,1\n",
    "        f_1,f_2=1,0\n",
    "        for i in range(1,n):\n",
    "            f_1,f_2=f_2,i*(f_1+f_2)%1000000007\n",
    "        return f_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        f = [0 for _ in range(0, 3)]\n",
    "        f[0] = 1\n",
    "        f[1] = 0\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, n + 1):\n",
    "            f[2] = (i - 1) * (f[1] + f[0]) % 1000000007\n",
    "            f[0] = f[1]\n",
    "            f[1] = f[2]\n",
    "        return f[2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        #f(n) = (n-1) * (f(n-1) + f(n-2))\n",
    "        f1 = 0\n",
    "        f2 = 1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        m = 10**9 + 7\n",
    "        for i in range(3, n+1):\n",
    "            f2, f1 = (i-1) * (f1+f2) % m, f2\n",
    "        return f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        if n==1 or n==2 or n==3:\n",
    "            return n-1\n",
    "        num1=1\n",
    "        num2=2\n",
    "        for i in range(4,n+1):\n",
    "            num=(i-1)*(num1+num2)%(10**9+7)\n",
    "            num1=num2\n",
    "            num2=num\n",
    "        return num\n",
    "            \n",
    "    \n",
    "               \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "      a, b = 1, 0\n",
    "      MOD = int(1e9 + 7)\n",
    "\n",
    "      for i in range(2, n + 1):\n",
    "        a, b = b, (i - 1) * (a + b) % MOD\n",
    "\n",
    "      return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        p = [0, 1]\n",
    "        if n <= 2: return p[n-1]\n",
    "        for id in range(2,n):\n",
    "            p[0], p[1] = p[1], id * (p[0] + p[1]) % int(1e9+7)\n",
    "        return p[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        #动态规划f(n) = (n - 1) * (f(n - 1) + f(n - 2)),f(n-2)的情况代表两数对调,f(n-1)的情况代表非对调情况\n",
    "        #初始情况n=2,1\n",
    "        f_1,f_2=1,0\n",
    "        for i in range(1,n):\n",
    "            f_1,f_2=f_2,i*(f_1+f_2)%(10**9+7)\n",
    "        return f_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        #动态规划f(n) = (n - 1) * (f(n - 1) + f(n - 2)),f(n-2)的情况代表两数对调,f(n-1)的情况代表非对调情况\n",
    "        #初始情况n=2,1\n",
    "        f_1,f_2=1,0\n",
    "        if n>1:\n",
    "            for i in range(2,n):\n",
    "                f_1,f_2=i*(f_1+f_2)%(10**9+7),f_1\n",
    "        else:\n",
    "            f_1=0\n",
    "        return f_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        # f(n) = (n - 1)*(f(n - 1) + f(n - 2))\n",
    "        # 以n = 4,[1,2,3,4]为例，第一位可以从2，3，4中选择(n - 1)，假设选择2，那么第二位可以选择1，或者选择3，4\n",
    "        # 如果选择1，那问题变成了[3,4]的错位排列(n-2)子问题，如果不选择1，那问题变成[1,3,4]的错位排列问题（n - 1）\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        MOD = 10**9 + 7\n",
    "        x,y = 0,1\n",
    "        for i in range(3,n + 1):\n",
    "            y,x = (i - 1)*(y + x)%MOD,y\n",
    "        \n",
    "        return y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        k=0\n",
    "        flag = 1\n",
    "        for i in range(2,n+1):\n",
    "            k=(k*i+flag)%(10**9+7)\n",
    "            flag = -flag\n",
    "        return k%(10**9+7)\n",
    "        # mul = 1\n",
    "        # sum=0\n",
    "        # M = (10**9+7)\n",
    "        # for i in range(n,-1,-1):\n",
    "        #     sum = (sum+M+mul*(1 if i%2==0 else -1))%M\n",
    "        #     mul = (mul*i)%M\n",
    "        # return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        # 元素n有n - 1个位置可以放置，因此有n - 1种方法\n",
    "        # 将n放在k的位置，假设我们把k放在n位置，则还剩余n-2的子问题，否则是n-1的子问题\n",
    "        mod = 10 ** 9 + 7\n",
    "        if n < 2: return 0\n",
    "        pre0 = 0\n",
    "        pre1 = 1\n",
    "        for i in range(3, n + 1):\n",
    "            cur = (i - 1) * (pre0 + pre1)\n",
    "            cur %= mod\n",
    "            pre0, pre1 = pre1, cur\n",
    "\n",
    "        return pre1 \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # MOD = 10 ** 9 + 7\n",
    "\n",
    "        # if n == 1: return 0\n",
    "        \n",
    "        # prev1 = 0\n",
    "        # prev2 = 1\n",
    "        # for i in range(3, n + 1):\n",
    "        #     current = (i - 1) * (prev1 + prev2)\n",
    "        #     current %= MOD\n",
    "        #     prev1, prev2 = prev2, current\n",
    "        \n",
    "        # return prev2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        a = 0\n",
    "        b = 1\n",
    "        for i in range(3, n+1):\n",
    "            b, a = a * (i-1) + b * (i-1), b\n",
    "            b = b % int(1e9+7)\n",
    "            a = a % int(1e9+7)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        pre, cnt = 0, 1\n",
    "        if n == 1: return 0\n",
    "        if n == 2: return 1\n",
    "        for i in range(2, n):\n",
    "            pre, cnt = cnt, (pre + cnt) * i % int(1e9+7)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        mod = pow(10, 9) + 7\n",
    "        res = 0\n",
    "        for i in range(2, n + 1):\n",
    "            res = ((res * i) + ((-1) if i % 2 else 1)) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        a, b = 0, 1\n",
    "        for i in range(3, n+1):\n",
    "            a, b = b, (i-1) *(a + b) % (10 **9 + 7)\n",
    "        return b % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        # a[n] = (a[n-1] + a[n-2]) * (n-1)\n",
    "        MOD = 10**9+7\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        dp_1, dp_0 = 1, 0\n",
    "        for i in range(3, n+1):\n",
    "            dp_1, dp_0 = (i-1)*(dp_1+dp_0)%MOD,dp_1\n",
    "\n",
    "        return dp_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        # 元素n有n - 1个位置可以放置，因此有n - 1种方法\n",
    "        # 将n放在k的位置，假设我们把k放在n位置，则还剩余n-2的子问题，否则是n-1的子问题\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        if n == 1: return 0\n",
    "        \n",
    "        prev1 = 0\n",
    "        prev2 = 1\n",
    "        for i in range(3, n + 1):\n",
    "            current = (i - 1) * (prev1 + prev2)\n",
    "            current %= MOD\n",
    "            prev1, prev2 = prev2, current\n",
    "        \n",
    "        return prev2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        # 元素n有n - 1个位置可以放置，因此有n - 1种方法\n",
    "        # 将n放在k的位置，假设我们把k放在n位置，则还剩余n-2的子问题，否则是n-1的子问题\n",
    "\n",
    "        if n < 2: return 0\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        pre1 = 0\n",
    "        pre2 = 1\n",
    "\n",
    "        for i in range(3, n + 1):\n",
    "            current = (i - 1) * (pre2 + pre1) % MOD\n",
    "            pre1 = pre2\n",
    "            pre2 = current\n",
    "\n",
    "        return pre2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # MOD = 10 ** 9 + 7\n",
    "\n",
    "        # if n == 1: return 0\n",
    "        \n",
    "        # prev1 = 0\n",
    "        # prev2 = 1\n",
    "        # for i in range(3, n + 1):\n",
    "        #     current = (i - 1) * (prev1 + prev2)\n",
    "        #     current %= MOD\n",
    "        #     prev1, prev2 = prev2, current\n",
    "        \n",
    "        # return prev2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "mx = 10 ** 6 \n",
    "f = [0] * (mx + 1)\n",
    "f[2] = 1\n",
    "\n",
    "for i in range(3, mx + 1):\n",
    "    f[i] = (f[i - 1] + f[i - 2]) * (i - 1) % mod \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "dp = [0] * (10 ** 6 + 1)\n",
    "dp[1], dp[2] = 0, 1\n",
    "for i in range(3, 10 ** 6 + 1):\n",
    "    dp[i] = (i - 1) * (dp[i-1] + dp[i-2]) % MOD\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "m = 10**9 + 7\n",
    "dp = [0, 0, 1]\n",
    "for i in range(3, 10**6 + 1):\n",
    "    dp.append((i - 1) * (dp[-1] + dp[-2]) % m)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % m\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        # mod=10**9+7\n",
    "        # n=1->0\n",
    "        # n=2->1\n",
    "\n",
    "        # n=3->2\n",
    "        # n=4 [1,2,3,4] -> [2,1,4,3]+[2,3,4,1]+[2,4,1,3] 9\n",
    "\n",
    "# class Solution:\n",
    "#     def findDerangement(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        dp[0] = 1\n",
    "        dp[1] = 0\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = (i - 1) * (dp[i-2] + dp[i - 1])\n",
    "            dp[i] %= 1000000007\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        mod = 1000000007\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        dp[1] = 0\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n + 1):\n",
    "            dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])\n",
    "            dp[i] %= mod\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0], dp[1] = 1, 0\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % (10 ** 9 + 7)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "\n",
    "        f = [0]*(n+1)\n",
    "        f[0] = 1\n",
    "        for i in range(2, n+1):\n",
    "            f[i] = (i-1)*(f[i-1]+f[i-2])%1000000007\n",
    "\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        m = 10**9 + 7\n",
    "        dp = [0, 0, 1]\n",
    "        for i in range(3, n+1):\n",
    "            dp.append((i - 1) * (dp[-1] + dp[-2]) % m)\n",
    "\n",
    "        return dp[n]\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        m = 10 ** 9 + 7\n",
    "        dp[0] = 1\n",
    "        dp[1] = 0\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = (i - 1) * (dp[i-1] + dp[i-2])\n",
    "            dp[i] %= m\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        dp[0] = 1\n",
    "        dp[1] = 0\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = (i - 1) * (dp[i-2] + dp[i - 1])\n",
    "            dp[i] %= 1000000007\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        if n == 1:\n",
    "            return 0 \n",
    "        if n == 2:\n",
    "            return 1\n",
    "        \n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 0\n",
    "        dp[2] = 1\n",
    "\n",
    "        for i in range(3, n + 1):\n",
    "            dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % mod\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        dp = [0]*n\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n):\n",
    "            dp[i] = ((dp[i-1] + dp[i-2])*i)%MOD\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        if n == 1:return 0\n",
    "        dp = [0]*(n+1)\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n+1):\n",
    "            dp[i] = ((dp[i-2] + dp[i-1]) * (i-1)) % (10**9 + 7)\n",
    "\n",
    "        return dp[-1] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 0\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = (i-1) * (dp[i-2] + dp[i-1])\n",
    "            dp[i] = dp[i] % (10 ** 9 + 7)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "\n",
    "        dp = [0] * n\n",
    "        CONST = 10**9+7\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n):\n",
    "            dp[i] = (i) * (dp[i-1] + dp[i-2]) % CONST\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 0\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = ((i-1) * (dp[i-1] + dp[i-2])) % (10**9+7)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        # 元素n有n - 1个位置可以放置，因此有n - 1种方法\n",
    "        # 将n放在k的位置，假设我们把k放在n位置，则还剩余n-2的子问题，否则是n-1的子问题\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        if n == 1: return 0\n",
    "        dp[1] = 0\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n + 1):\n",
    "            dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])\n",
    "            dp[i] %= MOD\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        mod = 1e9+7\n",
    "        a = [0] * max(4, (n+1))\n",
    "        a[0] = 0\n",
    "        a[1] = 0\n",
    "        a[2] = 1\n",
    "        a[3] = 2\n",
    "        for i in range(4, n+1):\n",
    "            a[i] = (i-1) * (a[i-1] + a[i-2]) % mod\n",
    "        return int(a[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        # 元素n有n - 1个位置可以放置，因此有n - 1种方法\n",
    "        # 将n放在k的位置，假设我们把k放在n位置，则还剩余n-2的子问题，否则是n-1的子问题\n",
    "\n",
    "        if n < 2: return 0\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = dp[1] = 0\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n + 1):\n",
    "            dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # MOD = 10 ** 9 + 7\n",
    "\n",
    "        # if n == 1: return 0\n",
    "        \n",
    "        # prev1 = 0\n",
    "        # prev2 = 1\n",
    "        # for i in range(3, n + 1):\n",
    "        #     current = (i - 1) * (prev1 + prev2)\n",
    "        #     current %= MOD\n",
    "        #     prev1, prev2 = prev2, current\n",
    "        \n",
    "        # return prev2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        m = 10**9 + 7\n",
    "        dp=[0,0,1]\n",
    "        for i in range(3, n+1):\n",
    "            dp.append((i - 1) * (dp[-1] + dp[-2]) % m)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        if n ==1: return 0\n",
    "        if n==2: return 1\n",
    "        MOD = 10**9+7\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0:3] = 0,0,1\n",
    "        for i in range(3,n+1):\n",
    "            dp[i] = (i-1)*(dp[i-1] + dp[i-2])%MOD\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        dp[2] = 1\n",
    "        #print(dp)\n",
    "        for i in range(3, n + 1):\n",
    "            dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])\n",
    "            #print(i, dp[i], dp)\n",
    "            dp[i] %= MOD\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDerangement(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        nums = [1,0]\n",
    "        for i in range(n-1):\n",
    "            nums.append((i+1)*(nums[-1]+nums[-2]))\n",
    "            nums[-1] %= mod\n",
    "        return nums[-1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
